package leetcode.offer_two_special.backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * @author mazouri
 * @create 2021-09-20 13:11
 */
public class _87_restoreIpAddresses {
    String s;
    List<String> res = new LinkedList<>();
    int pointNum = 0;

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0) return res;

        this.s = s;
        backtrack(0);
        return res;
    }

    private void backtrack(int start) {
        if (pointNum == 3) {
            if (isValid(start, s.length() - 1)) {
                res.add(s);
            }
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (!isValid(start, i)) break;

            pointNum++;
            s = s.substring(0, i + 1) + "." + s.substring(i + 1);
            backtrack(i + 2);
            s = s.substring(0, i + 1) + s.substring(i + 2);
            pointNum--;
        }

    }

    private boolean isValid(int start, int end) {
        if (start > end) return false;

        // 0开头的数字不合法
        if (s.charAt(start) == '0' && start != end) return false;

//        for (int i = start; i <= end; i++) {
//            if (s.charAt(start) > '9' || s.charAt(end) < '0') return false;
//        }
//
//        return Double.parseDouble(s.substring(start, end+1)) <= 255;
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new _87_restoreIpAddresses().restoreIpAddresses("0279245587303"));
    }
}
